package pro.softzhang.algo.lc1300;

import pro.softzhang.algo.flag.book.BDaily;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

@BDaily
public class LC1376_TimeNeededToInformAllEmployees {
    public static void main(String[] args) {

    }

    static
    class Solution {
        public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
            Map<Integer, List<Integer>> m = new HashMap<>();
            for(int i = 0; i < n; i++) {
                m.putIfAbsent(manager[i], new ArrayList<>());
                m.get(manager[i]).add(i);
            }
            return dfs(headID, informTime, m);
        }

        private int dfs(int workerId, int[] informTime, Map<Integer, List<Integer>> m) {
            int time = 0;
            for(int child : m.getOrDefault(workerId, new ArrayList<>())) {
                time = Math.max(time, dfs(child, informTime, m));
            }
            return informTime[workerId] + time;
        }
    }
}
